package leetcode.dandiaostack;

import java.util.Stack;

public class Test2 {
    public static void main(String[] args) {
        int[] prices = {8, 4, 6, 2, 3};
        int[] finalPrices = finalPrices(prices);
        for (int i = 0; i < finalPrices.length; i++) {
            System.out.println(finalPrices[i]);
        }
    }

    public static int[] finalPrices(int[] prices) {
        int[] result = new int[prices.length];
        Stack<Integer> stack = new Stack<>();
        stack.push(prices.length - 1);
        result[prices.length - 1] = prices[prices.length - 1];
        for (int i = prices.length - 2; i >= 0; i--) {
            int pop = stack.peek();
            while (!stack.isEmpty() && prices[i] < prices[pop]) {
                pop = stack.pop();
            }
            if (prices[i] > prices[pop]) {
                result[i] = prices[i] - prices[pop];
            } else {
                result[i] = prices[i];
            }
            stack.push(i);
        }
        return result;
    }
}
